// 分治 快排 数组划分、数组分块
// 使用 3 指针将数组分为 4 块：[0, left], [left + 1, cur], [cur, right - 1], [right, n - 1]
// [0, left] - left 维护的区间
// [left + 1, cur] - cur 维护的区间
// [cur, right - 1] - 待处理的区间
// [right, n - 1] - right 维护的区间
// cur 负责扫描数组
// 快排的核心就是使用 三指针 方法，只是多了找基准元素的一步
// 找基准元素最优秀的方式就是区间内选择区间内的随机元素，时间复杂度可以逼近 O(n * log n)

// 例题 2：
// 给你一个整数数组 nums，请你将该数组升序排列。
// 你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
//
//        示例 1：
//
//        输入：nums = [5,2,3,1]
//        输出：[1,2,3,5]
//        示例 2：
//
//        输入：nums = [5,1,1,2,0,0]
//        输出：[0,0,1,1,2,5]
//
//
//        提示：
//
//        1 <= nums.length <= 5 * 104
//        -5 * 104 <= nums[i] <= 5 * 104

// 解题思路：
// 使用 三指针 数组划分作为快排的核心思想
// 在数组区间内随机找基准元素，进行快排

import java.util.Random;

public class SortArray {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        sort(nums, 0, n - 1);
        return nums;
    }
    public void sort(int[] nums, int start, int end){
        if(start == end) return;
        int left = start - 1; int right = end + 1;
        Random random = new Random();
        int index = random.nextInt(end - start + 1) + start;
        int key = nums[index];
        int cur = start;
        while(cur < right){
            if(nums[cur] < key) swap(nums, ++left, cur++);
            else if(nums[cur] > key) swap(nums, --right, cur);
            else cur++;
        }
        sort(nums, start, left);
        sort(nums, right, end);
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}